"""
752. 打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
"""
import collections
from typing import List


class Solution:

    def openLock(self, deadends: List[str], target: str) -> int:
        count = 0
        queue = collections.deque()
        # 记录需要跳过的死亡密码
        deads = set(deadends)
        # 记录已经穷举过的密码，防止走回头路
        visited = set()
        queue.append('0000')

        while queue:
            size = len(queue)
            for i in range(size):
                cur = queue.popleft()
                if cur in deads:
                    continue
                if cur == target:
                    return count

                for j in range(4):
                    up = self.up_one(cur, j)
                    if up not in visited:
                        queue.append(up)
                        visited.add(up)
                    down = self.down_one(cur, j)
                    if down not in visited:
                        queue.append(down)
                        visited.add(down)

            count += 1

        return -1

    def up_one(self, s: str, i: int) -> str:
        l = list(s)
        if l[i] == '9':
            l[i] = '0'
        else:
            l[i] = chr(ord(l[i]) + 1)
        return ''.join(l)

    def down_one(self, s: str, i: int) -> str:
        l = list(s)
        if l[i] == '0':
            l[i] = '9'
        else:
            l[i] = chr(ord(l[i]) - 1)
        return ''.join(l)


if __name__ == '__main__':
    sl = Solution()
    s = sl.up_one('1234', 0)
    print(s)